﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DiscoveryLogic.Analytics.DataObjects.Networks
{
    public class NetworkWalker
    {
        private Dictionary<Guid,Vertice> _Vertices;
        public Dictionary<Guid, Edge> _Edges;

        public NetworkWalker(List<Vertice> vertices, List<Edge> edges)
        {
            this._Vertices = new Dictionary<Guid, Vertice>();
            foreach(Vertice v in vertices)
                this._Vertices.Add(v.ID, v);
            this._Edges=new Dictionary<Guid, Edge>();
            foreach(Edge e in edges)
                this._Edges.Add(e.ID, e);
        }

        public Dictionary<Vertice, Route> GetShortestPathsFrom(Vertice srcVertice)
        {
            Dictionary<Vertice, Route> routes = new Dictionary<Vertice, Route>();
            List<Guid> handledLocations=new List<Guid>();
            foreach(Vertice v in this._Vertices.Values)
            {
                routes.Add(v, new Route(v.ID));
            }
            routes[srcVertice].Distance = 0;
            while(handledLocations.Count < routes.Count)
            {
                //Order the locations
                List<Vertice> neighbors =
                    (from s in routes
                     orderby s.Value.Distance
                     select s.Key).ToList();
                Vertice verticeToProcess = null;
                
                //Search for the nearest location that isn't handled
                foreach (Vertice neighbor in neighbors)
                {
                    if (!handledLocations.Contains(neighbor.ID))
                    {
                        //If the cost equals int.max, there are no more possible connections to the remaining locations
                        if (routes[neighbor].Distance == double.PositiveInfinity)
                            return routes;
                        verticeToProcess = neighbor;
                        break;
                    }
                }

                //Select all connections where the startposition is the location to Process
                var selectedConnections = from c in this._Edges.Values
                                          where c.VerticeID1 == verticeToProcess.ID || c.VerticeID2 == verticeToProcess.ID
                                          select c;

                //Iterate through all connections and search for a connection which is shorter
                foreach (Edge conn in selectedConnections)
                {
                    Guid vID1 = verticeToProcess.ID;
                    Guid vID2 = (conn.VerticeID1 == vID1) ? conn.VerticeID2 : conn.VerticeID1;
                    if (routes[this._Vertices[vID2]].Distance > conn.Length + routes[this._Vertices[vID1]].Distance)
                    {
                        routes[this._Vertices[vID2]].Edges = routes[this._Vertices[vID1]].Edges.ToList();
                        routes[this._Vertices[vID2]].Edges.Add(conn);
                        routes[this._Vertices[vID2]].Distance = conn.Length + routes[this._Vertices[vID1]].Distance;
                    }
                }

                //Add the location to the list of processed locations
                handledLocations.Add(verticeToProcess.ID);
            }

            return routes;
        }

        public Dictionary<Vertice, List<Route>> GetAllRoutesFrom(Vertice srcVertice, int maxHop)
        {
            Dictionary<Vertice,List<Route>> allRoutesFrom=new Dictionary<Vertice, List<Route>>();
            foreach(Vertice toVertice in this._Vertices.Values)
            {
                if(toVertice==srcVertice)
                    continue;

                List<Route> toRoutes=new List<Route>();
                Stack<Vertice> visitedVertices = new Stack<Vertice>();
                visitedVertices.Push(srcVertice);
                Stack<Edge> visitedPaths = new Stack<Edge>();
                this.Walk(srcVertice, toVertice, maxHop, ref toRoutes, visitedVertices, visitedPaths);
                if(toRoutes.Count>0)
                    allRoutesFrom.Add(toVertice, toRoutes);
            }
            return allRoutesFrom;
        }

        public List<Route> GetAllRoutesBetween(Vertice fromV, Vertice toV, int maxHop)
        {
            List<Route> toRoutes = new List<Route>();
            Stack<Vertice> visitedVertices = new Stack<Vertice>();
            visitedVertices.Push(fromV);
            Stack<Edge> visitedPaths = new Stack<Edge>();
            this.Walk(fromV, toV, maxHop, ref toRoutes, visitedVertices, visitedPaths);
            return toRoutes;
        }

        private bool Walk(
            Vertice fromVertice, 
            Vertice toVertice, int maxHop,
            ref List<Route> routes, 
            Stack<Vertice> visitedVertices,
            Stack<Edge> visitedPaths)
        {
            bool foundPath = false;
            foreach(Edge e in this._Edges.Values)
            {
                Vertice nextV = null;
                if(e.VerticeID1==fromVertice.ID)
                {
                    nextV = this._Vertices[e.VerticeID2];
                }
                else if(e.VerticeID2==fromVertice.ID)
                {
                    nextV = this._Vertices[e.VerticeID1];
                }
                if(nextV==null)
                    continue;

                if(nextV==toVertice)
                {
                    List<Edge> correctPath=new List<Edge>();
                    correctPath.AddRange(visitedPaths);
                    correctPath.Add(e);
                    Route route = this.ToRoute(toVertice, correctPath);
                    routes.Add(route);
                    foundPath = true;
                    break;
                }
                else if(!visitedVertices.Contains(nextV))
                {
                    if (visitedPaths.Count > maxHop)
                        break;

                    visitedPaths.Push(e);
                    visitedVertices.Push(nextV);
                    foundPath = this.Walk(nextV, toVertice, maxHop, ref routes, visitedVertices, visitedPaths);
                    visitedVertices.Pop();
                }
            }
            if (visitedPaths.Count>0)
                visitedPaths.Pop();
            
            return foundPath;
        }

        private Route ToRoute(Vertice toV, List<Edge> visitedPaths)
        {
            if (visitedPaths.Count < 1)
                return null;
            Route route = new Route(toV.ID);
            route.Edges = visitedPaths;
            route.Distance = 0;
            foreach(Edge e in visitedPaths)
                route.Distance += e.Length;
            return route;
        }
    }

    public class Route
    {
        private List<Edge> _Edges;
        public List<Edge> Edges
        {
            get
            {
                return _Edges;
            }
            set
            {
                _Edges = value;
            }
        }
        private double _Distance;
        public double Distance
        {
            get
            {
                return _Distance;
            }
            set
            {
                _Distance = value;
            }
        }
        private Guid _DestinationID;
        /// <summary></summary>
        public Guid DestinationID
        {
            get
            {
                return this._DestinationID;
            }
            set
            {
                this._DestinationID = value;
            }
        }

        public Route(Guid destID)
        {
            this._DestinationID = destID;
            this._Edges=new List<Edge>();
            this._Distance = double.PositiveInfinity;
        }

        public Route(Guid destID, List<Edge> path, double distance):this(destID)
        {
            this._Edges = path;
            this._Distance = distance;
        }
    }
}
